#include "Graph.h"

/*在庞大的边数量面前，直接使用节点类型的优先队列会浪费大量空间
而如果使用「节点指针」类型，在遇到重复边时会影响优先队列排序
从而造成错误结果，除非能自己写一个优先队列（也就是二叉堆）*/

/*如果想既不写堆也能应付更多边情况，那就减小堆中元素的类型，这里
提供的类就可以做到，只保留图节点下标和其权重*/

struct AnsCmp
{
    int nodeId;//节点下标
    int weight;//加入堆时节点的权重
    bool operator<(const AnsCmp &a)const
    {
        //C++默认是大顶堆，想直接修改成小顶堆，可以反着重写<的逻辑
        return a.weight < weight; 
        /*当this.weight > a.weight时，反而this比较「小」
        所以weight < a.weight是「大」的，会在堆顶，从而构建小顶堆*/
    }
};

//适用于单源最短路径问题，且无负边
void DijkstraShortestPath(Graph* g, int start, int target)
{
    priority_queue<AnsCmp> pq;//记录各节点
    unordered_set<int> mark;//标记已访问过的节点
    g->nodeSet[start]->weight = 0;
    pq.push(AnsCmp{start, 0});
    while(!pq.empty())
    {
        auto cur = pq.top().nodeId;
        pq.pop();
        if(mark.count(cur))//跳过已访问点
            continue;
        mark.insert(cur);
        for(auto e : g->nodeSet[cur]->edges)
        {
            auto t = e->to;
            int dist = e->weight + g->nodeSet[cur]->weight;
            if(dist < t->weight)
            {
                t->weight = dist;
                //防止重复边，故而每次都用新的AnsCmp
                pq.push(AnsCmp{t->value, t->weight});
            }
        }
    }
}